English+GermanWikipedia - /page/entry.mu

<!DOCTYPE html>

<title>Aggregat-Methode</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Aggregat-Methode</span></h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr"><p>Die <b>Aggregat-Methode</b> (auch <b>Aggregationsmethode</b> oder <b>Ganzheitsmethode</b>) ist ein Vorgehen der <a href="Amortisierte_Laufzeitanalyse" title="Amortisierte Laufzeitanalyse">amortisierten (Laufzeit-)Analyse</a>. Bei der Aggregat-Methode wird versucht die durchschnittlichen Kosten einer Einzeloperation zu ermitteln, indem man zunächst die Gesamtkosten aller Operationen ermittelt und diese dann durch die Anzahl der Operationen dividiert.

</p>

<div class="mw-heading mw-heading2"><h2 id="Beispiele">Beispiele</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Binärzähler"><span id="Bin.C3.A4rz.C3.A4hler"></span>Binärzähler</h3></div>

<p>Die Aggregat-Methode wird am Beispiel eines <a href="Dualsystem" title="Dualsystem">Binärzählers</a>, dessen einzig mögliche Operation eine <a href="Inkrement_und_Dekrement" title="Inkrement und Dekrement">Inkrementation</a> ist, durchgeführt.

</p><p>Der <a href="Worst_Case" title="Worst Case">Worst Case</a> bei einem Binärzähler mit <i>k</i> Bit tritt dann auf, wenn bei einer Inkrementation alle <i>k</i> Bit gekippt werden müssen. Seien die Kosten für einen Bitwechsel 1. Dann würden nach der Worst-Case-Abschätzung bei <i>n</i> Operationen Kosten von <i>nk</i> entstehen. Diese Abschätzung ist allerdings zu pessimistisch. Mittels der amortisierten Analyse wird versucht eine realistischere und weniger pessimistische Abschätzung der Kosten nach oben zu erreichen.

</p><p>Betrachten wir die Anzahl der Bitwechsel bei einem Zähler mit 4 Bit:

</p>

<th>Zähler</th>

<th>Anzahl Bitwechsel

</th></tr>

<tr>

<td>-

</td></tr>

<tr>

<td>1

</td></tr>

<tr>

<td>2

</td></tr>

<tr>

<td>1

</td></tr>

<tr>

<td>3

</td></tr>

<tr>

<td>1

</td></tr>

<tr>

<td>2

</td></tr>

<tr>

<td>1

</td></tr>

<tr>

<td>4

</td></tr>

<tr>

<td>

</td></tr></tbody></table>

<p>Wenn man sich die Folge der Bitwechsel anschaut, fällt auf, dass sich das niedrigste Bit bei jeder Inkrementation ändert, das nächsthöhere bei jeder zweiten, das wiederum nächsthöhere bei jeder vierten usw. Damit ergibt sich bei <i>n</i> Inkrementationen folgende Summe von Bitwechseln:

</p>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

<mrow>

<mfrac>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

</mrow>

<mrow>

<mfrac>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

</mrow>

<mrow>

<mfrac>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

</mrow>

</mrow>

</mrow>

</munderover>

<mfrac>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n+\left\lfloor {\frac {n}{2}}\right\rfloor +\left\lfloor {\frac {n}{2^{2}}}\right\rfloor +\left\lfloor {\frac {n}{2^{3}}}\right\rfloor +\cdots +\left\lfloor {\frac {n}{2^{k}}}\right\rfloor \leq n\sum _{i=0}^{k}{\frac {1}{2^{i}}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/40218d90db69bd40abb660988d10f0fe553de855.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:51.751ex; height:7.343ex;" alt="{\displaystyle n+\left\lfloor {\frac {n}{2}}\right\rfloor +\left\lfloor {\frac {n}{2^{2}}}\right\rfloor +\left\lfloor {\frac {n}{2^{3}}}\right\rfloor +\cdots +\left\lfloor {\frac {n}{2^{k}}}\right\rfloor \leq n\sum _{i=0}^{k}{\frac {1}{2^{i}}}}" loading="lazy"></span>

</p>

</div>

<p>Diese Summe können wir nach oben abschätzen:

</p>

</mrow>

</mrow>

</munderover>

<mfrac>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

</mrow>

</mrow>

</munderover>

<mfrac>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n\sum _{i=0}^{k}{\frac {1}{2^{i}}}\leq n\sum _{i=0}^{\infty }{\frac {1}{2^{i}}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3bd023d6aa50ab6ee3ba71fc7b21aff2dbaccd08.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:19.743ex; height:7.343ex;" alt="{\displaystyle n\sum _{i=0}^{k}{\frac {1}{2^{i}}}\leq n\sum _{i=0}^{\infty }{\frac {1}{2^{i}}}}" loading="lazy"></span>

</p>

</div>

<p>Die Summe dieser <a href="Unendliche_Reihe" class="mw-redirect" title="Unendliche Reihe">unendlichen Reihe</a> ist wohlbekannt und lautet 2. Daraus folgt:

</p>

</mrow>

</mrow>

</munderover>

<mfrac>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n\sum _{i=0}^{k}{\frac {1}{2^{i}}}\leq 2n}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6439b8798930f690a4f22a6be08dcd49489dc862.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:13.978ex; height:7.343ex;" alt="{\displaystyle n\sum _{i=0}^{k}{\frac {1}{2^{i}}}\leq 2n}" loading="lazy"></span>

</p>

</div>

<p>Betrachten wir nun die amortisierten Kosten <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{i}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0bc77764b2e74e64a63341054fa90f3e07db275f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.029ex; height:2.009ex;" alt="{\displaystyle a_{i}}" loading="lazy"></span> für eine einzelne Operation <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Op_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Op_{i}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/cb08f6e0407129d15bcf8069a17ae4e8f673e6ed.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.742ex; height:2.509ex;" alt="{\displaystyle Op_{i}}" loading="lazy"></span> der insgesamt <i>n</i> Operationen, indem wir die bereits ermittelten Gesamtkosten durch die Anzahl <i>n</i> der Operationen teilen, erhalten wir:

</p>

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{i}\leq {\frac {2n}{n}}=2}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9c5cf16c1cabefd6d19a1cfd7737b24caeca8710.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:12.782ex; height:5.176ex;" alt="{\displaystyle a_{i}\leq {\frac {2n}{n}}=2}" loading="lazy"></span></div>

<p>Damit sind die amortisierten Kosten für eine Operation höchstens 2 und somit in <a href="Landau-Symbol" class="mw-redirect" title="Landau-Symbol">O</a>(1), egal, wie viele Bits der Zähler insgesamt hat.

</p>

<div class="mw-heading mw-heading3"><h3 id="Wörterbuch"><span id="W.C3.B6rterbuch"></span>Wörterbuch</h3></div>

<p>Eine außerordentlich verbreitete Sorte von Datenstrukturen sind die binären Suchbäume. Sie lösen bspw. das “Wörterbuch”problem (s. <a href="Bin%C3%A4rer_Suchbaum#Motivation" title="Binärer Suchbaum">Binärer Suchbaum#Motivation</a>), und zwar die balancierten unter ihnen die wichtigsten Operationen im schlechtesten Fall (<i>worst case</i>) in logarithmischer Zeit. Eine Aussage über amortisiertes Laufzeitverhalten findet sich ggf. im entsprechenden Artikel.

</p><p>Hier werde eine Datenstruktur, genannt <i>amortisierte Wörterbuch-Datenstruktur</i> (englisch <i>amortized dictionary data structure</i><sup id="cite_ref-CMU_1-0" class="reference"><a href="#cite_note-CMU-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>), vorgestellt, deren amortisiertes Laufzeitverhalten für das Suchen in <span style="white-space:nowrap"><i>O</i>(log<sup>2</sup> <i>n</i>)</span> und für das Einfügen in <span style="white-space:nowrap"><i>O</i>(log <i>n</i>)</span> ist.

</p><p>Die Anzahl <i>n</i> der Einträge sei in der binären Darstellung:

</p>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=:\sum _{i=0}^{k}\lambda _{i}2^{i}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5ea018059d3fc0c40df5a57a3bf18505dd4e120.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:12.999ex; height:7.343ex;" alt="{\displaystyle n=:\sum _{i=0}^{k}\lambda _{i}2^{i}}" loading="lazy"></span> mit <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda _{i}\in \{0,1\}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda _{i}\in \{0,1\}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/cd1fed4979584abded515e9cb7fcd2595d008017.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.679ex; height:2.843ex;" alt="{\displaystyle \lambda _{i}\in \{0,1\}}" loading="lazy"></span></dd></dl>

<p>Die Datenstruktur besteht dann aus <i>k</i>+1 sortierten Folgen, die entweder ganz leer (λ<sub>i</sub>=0) oder ganz voll (λ<sub>i</sub>=1) sind. Die einzelnen Elemente der Datenstruktur werden beliebig auf diese Folgen verteilt.

</p><p>Beispiel:

Es sei <i>n</i> = 11 (dann ist 11 = 1 + 2 + 8 und <i>k</i> = 3). Die Elemente seien <b>C</b>, <b>D</b>, <b>E</b>, <b>F</b>, <b>H</b>, <b>J</b>, <b>M</b>, <b>P</b>, <b>S</b>, <b>W</b> und <b>Y</b>, die wie folgt über die Datenstruktur verteilt seien:

</p>

<td>λ<sub>0</sub> = 1

</td></tr>

<tr>

<td>λ<sub>1</sub> = 1

</td></tr>

<tr>

<td>λ<sub>2</sub> = 0

</td></tr>

<tr>

<td>λ<sub>3</sub> = 1

</td></tr></tbody></table></dd></dl>

<p>Eine Suchoperation geschieht durch binäres Suchen in jeder Folge Λ<sub>i</sub> dar, plus einer logischen Zusammenfassung, so dass sich im schlechtesten Fall das Laufzeitverhalten

</p>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{i=0}^{k}\lambda _{i}\lceil \log(2^{i}+1)\rceil +k+1=\sum _{i=0}^{k}\lambda _{i}(i+1)+k+1}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2c04f820b12030659542c4df4b8e6d88b0ab843d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:50.427ex; height:7.343ex;" alt="{\displaystyle \sum _{i=0}^{k}\lambda _{i}\lceil \log(2^{i}+1)\rceil +k+1=\sum _{i=0}^{k}\lambda _{i}(i+1)+k+1}" loading="lazy"></span> = <i>O</i>(log<sup>2</sup> <i>n</i>)</dd></dl>

<p>ergibt.

</p><p>Eine Einfügung verwendet <a href="Mergesort" title="Mergesort">Mergesort</a>, dessen Aufwand durch die Summe der beiden Längen gegeben ist. Um den Buchstaben <b>K</b> einzufügen, wird eine Folge Λ der Länge 1 mit dem Inhalt <b>K</b> gebildet. Ist nun Λ<sub>0</sub> leer (Häufigkeit 1/2), machen wir Λ zu Λ<sub>0</sub> und sind fertig. Wenn nicht (wie im obigen Beispiel) (Häufigkeit 1/2), mischen (englisch <i>merge</i>) wir Λ mit Λ<sub>0</sub> mit Aufwand 1 + 1; der Name des Ergebnisses sei wieder Λ. Ist dann Λ<sub>1</sub> leer (Häufigkeit 1/4), machen wir Λ zu Λ<sub>1</sub> und sind fertig. Wenn nicht (Häufigkeit 1/4), mischen wir Λ mit Λ<sub>1</sub> mit Aufwand 2 + 2 und neuem Namen Λ. Ist dann Λ<sub>2</sub> leer (wie im obigen Beispiel) (Häufigkeit 1/8), machen wir Λ zu Λ<sub>2</sub> und sind fertig. Wenn nicht (Häufigkeit 1/8), geht es weiter wie gehabt. Im obigen Beispiel ergibt die Einfügung von <b>K</b>:

</p>

<td>λ<sub>0</sub> = 0

</td></tr>

<tr>

<td>λ<sub>1</sub> = 0

</td></tr>

<tr>

<td>λ<sub>2</sub> = 1

</td></tr>

<tr>

<td>λ<sub>3</sub> = 1

</td></tr></tbody></table></dd></dl>

<p>Der Gesamtaufwand ist maximal

</p>

<dl><dt>Ergebnis</dt></dl>

<p>Bei der vorgestellten Datenstruktur sind die amortisierten Kosten für eine Einfügung in <span style="white-space:nowrap"><i>O</i>(log <i>n</i>)</span>.

</p>

<dl><dt>Bemerkung</dt></dl>

<p>Sie sind damit nicht besser als bei <a href="AVL-Baum" title="AVL-Baum">AVL-</a> oder <a href="Rot-Schwarz-Baum" title="Rot-Schwarz-Baum">Rot-Schwarz-Bäumen</a>, bei denen reine Einfügungen (reine Baumänderungen) amortisiert konstant sind, das Aufsuchen der Einfügeposition mit <span style="white-space:nowrap"><i>O</i>(log <i>n</i>)</span> aber noch hinzugerechnet werden muss.<br>Bemerkenswerterweise sind die Einfügekosten jedoch kleiner als zugehörige reine Suchkosten.

</p>

<div class="mw-heading mw-heading2"><h2 id="Abgrenzung">Abgrenzung</h2></div>

<p>Im Gegensatz zur <a href="Account-Methode" title="Account-Methode">Account-Methode</a> werden bei der Aggregat-Methode die amortisierten Kosten auch von unterschiedlichen Arten von Operationen gleichgesetzt. D. h., mit der Account-Methode können verschiedenen Arten von Operationen unterschiedliche amortisierte Kosten zugeordnet werden. Außerdem wird bei der Account-Methode die Differenz zwischen amortisierten und realen Kosten auf einem Konto gebucht.

</p>

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li>Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Introduction to Algorithms</cite>. 2. Auflage. MIT Press and McGraw-Hill, 2001, ISBN 0-262-03293-7, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em"> </span>406–410</span> (englisch).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Aggregat-Methode&rft.au=Thomas+H.+Cormen%2C+Charles+E.+Leiserson%2C+Ronald+L.+Rivest%2C+...&rft.btitle=Introduction+to+Algorithms&rft.date=2001&rft.edition=2.&rft.genre=book&rft.isbn=0262032937&rft.pages=406-410&rft.pub=MIT+Press+and+McGraw-Hill" style="display:none"> </span></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-CMU-1"><span class="mw-cite-backlink"><a href="#cite_ref-CMU_1-0">↑</a></span> <span class="reference-text"><span class="cite"><a rel="nofollow" class="external text" href="https://www.cs.cmu.edu/afs/cs/academic/class/15451-s07/www/lecture_notes/lect0206.pdf"><i>Lecture 7: Amortized Analysis.</i></a> In: <i><a rel="nofollow" class="external free" href="https://www.cs.cmu.edu/">https://www.cs.cmu.edu/</a>.</i><span class="Abrufdatum"> Abgerufen am 4. Oktober 2016</span> (englisch).</span><span style="display: none;" class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adc&rfr_id=info%3Asid%2Fde.wikipedia.org%3AAggregat-Methode&rft.title=Lecture+7%3A+Amortized+Analysis&rft.description=Lecture+7%3A+Amortized+Analysis&rft.identifier=&rft.date=&rft.language=en"> </span></span>

</li>

</ol></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2024-12-15" href="https://de.wikipedia.org/wiki/?title=Aggregat-Methode&oldid=251266865">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>